A = [(1.33, 2.1), (1.2, 2.63), (1.77, 2.8), (1.1, 2.1), (1.4, 2.3), (1.6, 2.53), (1.13, 3.07), (2.5, 2.87), (2.2, 2.13),
     (1.6, 1.77), (1.8, 2.13), (2.07, 2.43), (2.0, 2.8), (1.63, 3.07), (1.47, 2.9), (1.73, 3.2), (2.37, 3.07),
     (2.5, 2.13), (2.33, 2.57), (1.5, 2.47), (1.87, 2.4), (2.0, 3.03), (2.43, 2.57)]
B = [(1.27, 0.87), (1.77, 1.13), (2.77, 0.43), (1.93, 0.23), (1.7, 0.63), (2.3, 0.97), (2.4, 1.13), (2.5, 0.7),
     (2.07, 1.23), (2.6, 1.37), (1.0, 1.07), (1.5, 0.3), (1.77, 0.7), (1.63, 0.87), (2.2, 0.73), (2.33, 0.37),
     (1.97, 1.13), (2.13, 0.63), (2.07, 0.37), (2.03, 0.87), (1.97, 0.83), (1.6, 0.87), (1.53, 1.1), (1.5, 1.13),
     (1.5, 1.13), (2.17, 1.1), (2.27, 1.2), (2.3, 1.2), (2.83, 0.7), (2.97, 1.1), (2.8, 1.1), (2.8, 0.8)]
C = [(3.73, 2.7), (4.4, 2.73), (4.87, 1.53), (4.33, 1.7), (3.97, 2.27), (3.73, 2.57), (4.37, 2.67), (4.6, 2.1),
     (3.9, 2.6), (3.93, 2.63), (3.93, 2.63), (4.8, 2.3), (4.6, 2.43), (4.23, 2.53), (4.17, 2.23), (4.37, 2.3),
     (4.4, 2.47), (3.97, 2.17), (3.63, 1.87), (3.5, 2.23), (3.77, 2.43), (3.9, 1.7), (3.67, 1.5), (3.5, 1.57),
     (4.13, 1.3), (4.47, 1.23), (4.7, 1.47), (4.9, 1.77), (4.6, 1.9), (4.53, 1.5), (4.17, 1.43), (4.17, 1.87),
     (4.43, 1.93), (3.87, 1.93), (3.8, 2.13)]

data = []
# for x, y in A:
#     data.append((x, y, 'A'))
#
# for x, y in B:
#     data.append((x, y, 'B'))
#
# for x, y in C:
#     data.append((x, y, 'C'))

for pts, label in ((A, 'A'), (B, 'B'), (C, 'C')):
    for pt_x, pt_y in pts:
        data.append((pt_x, pt_y, label))


# 求距离
def distance(pt1, pt2):
    import math
    s1 = math.pow((pt1[0] - pt2[0]), 2)
    s2 = math.pow((pt1[1] - pt2[1]), 2)
    return math.sqrt(s1 + s2)


distances = []


def knn(data, point, k):
    labels = {}
    # 求出每个点与给定点的距离
    for pt_x, pt_y, label in data:
        if label not in labels:
            labels[label] = 0

        dis = distance((pt_x, pt_y), point)
        distances.append((dis, (pt_x, pt_y, label)))
    max_label = None
    # 统计K个最近的点的总和
    for _, (x, y, label) in sorted(distances, key=lambda e: e[0])[:k]:
        if max_label is None:
            max_label = (label, labels[label])

        labels[label] += 1
        if labels[label] > max_label[1]:
            max_label = (label, labels[label])

    print(labels)
    return max_label[0]

print(knn(data, (2.9, 1.77), 20))
